Problema do par de pontos mais próximo

Ilustração do par de pontos mais próximo.

O problema do par de pontos mais próximo consiste em, dado um conjunto de n pontos num espaço métrico, encontrar os dois pontos do conjunto que possuem a menor distância um do outro. A versão em duas dimensões, para pontos num plano, estava entre os primeiros problemas geométricos que foram tratados na origem do estudo de complexidade computacional de algoritmos geométricos.

Se forem computadas as distâncias entre todos os pares de pontos do conjunto, há n(n-1)/2 computações antes de ser possível decidir inequivocamente qual o par que apresenta a menor distância. Esse algoritmo é conhecido como força bruta e tem complexidade de tempo O(n²), ou seja, seu tempo de execução é proporcional ao quadrado do número de pontos do conjunto considerado. Porém, pesquisadores em geometria computacional descobriram que este problema pode ser resolvido em tempo O(n log n) em um espaço euclidiano ou espaço L^p de dimensão d fixa.

No modelo computacional que assume que a função chão é computada em tempo constante, o problema pode ser resolvido em tempo de O(n log log n). Se for permitido o uso de escolhas aleatórias em conjunto com a função chão, o problema pode ser resolvido em tempo O(n).

Problema no plano

O problema no plano pode ser resolvido em tempo de O(n log n) usando divisão e conquista, nos seguintes passos:

1. Ordenar os pontos de acordo com as coordenadas x;
2. Dividir o grupo de pontos em dois subgrupos de mesmo tamanho por uma linha vertical $x=x_{mid}$
3. Resolver o problema recursivamente para os dois grupos, resultando nas distâncias mínimas nos lados esquerdos e direitos, $d_{Emin}$ e $d_{Dmin}$ respectivamente.
4. Encontrar a distância mínima $d_{EDmin}$ entre um par de pontos onde cada ponto está em um lado diferente da linha vertical.
5. A resposta final é o mínimo entre $d_{Emin}$, $d_{Dmin}$, and $d_{EDmin}$.

Por sua vez, o quarto passo pode ser realizado em tempo linear, pois já sabemos que o par de pontos mais próximos não podem ter distância maior que $dist=\min(d_{Emin},d_{Dmin})$. Portanto para cada ponto p do lado esquerdo da linha vertical é feita a comparação das distâncias para pontos que estão do lado direito e dentro de um retângulo de dimensões (dist, 2 * dist), ou seja, pontos que possuem coordenada x com uma distância máxima dist para a direita de p e coordenada y com distância máxima dist para cima ou para baixo de p.

Considerando que o par de pontos mais próximos definem uma aresta na triangulação de Delaunay, e corresponde a duas faces adjacentes no diagrama de Voronoi, o par de pontos mais próximos pode ser determinado em tempo linear quando é dado junto ao problema uma dessas duas estruturas. Computar a triangulação de Delaunay, assim como o diagrama de Voronoi, leva tempo O(n log n). Porém para uma dimensão d maior que 2, esse tempo irá aumentar, enquanto que o algoritmo com divisão e conquista pode ser generalizado mantendo tempo O(n log n) para qualquer d.

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. P. 957–961 of section 33.4: Finding the closest pair of points.
• Jon Kleinberg; Éva Tardos (2006). Algorithm Design. [S.l.]: Addison Wesley 

Ligações externas

• UCSB Lecture Notes
• rosettacode.org - Closest pair of points implemented in multiple programming languages
• Line sweep algorithm for the closest pair problem